package org.zlb.algorithm.game;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.StringJoiner;

/**
 * 24点游戏
 * @author zhoulingbo
 * @date 2021/11/21
 */
public class Game24Point {
    
    public static final char ADD = '+';
    public static final char SUBTRACT = '-';
    public static final char MULTIPLY = '*';
    public static final char DIVIDE = '/';
    public static final char NONE = ' ';
    
    public static final int MIN = 1;
    public static final int MAX = 13;
    public static final int[] POKER = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
                                                 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
                                                 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
                                                 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};

    /**
     * 随机生成4个数
     * @return
     */
    public int[] random() {
        int[] arr = new int[4];
        for (int i=0; i<4; i++) {
            int r = (int)(Math.random() * 100);
            arr[i] = POKER[r%51];
        }
        return arr;
    }
    
    /**
     * 检查2个数通过+，-，*或/可得到24
     * @param a
     * @param b
     * @return
     */
    private char check(int a, int b) {
        if (a + b == 24)
            return ADD;
        if (a - b == 24)
            return SUBTRACT;
        if (a * b == 24)
            return MULTIPLY;
        if (b != 0 && a / b == 24 && a % b == 0)
            return DIVIDE;
        
        return NONE;
    }
    
    private List<Integer> calc(int a, int b) {
        List<Integer> list = new ArrayList<Integer>();
        list.add(a + b);
        list.add(a * b);
        
        if (a >= b)
            list.add(a - b);
        
        if (b != 0 && a >= b && a % b == 0)
            list.add(a / b);

        return list;
    }
    
    /**
     * 简化3个数，前2个数通过+，-，*或/运算得到新的数字
     * @param a
     * @param b
     * @param c
     * @return
     */
    private List<int[]> simplify(int a, int b, int c) {
        List<int[]> list = new ArrayList<>();
        
        List<Integer> subList = calc(a, b);
        for (Integer x : subList) {
            int[] item = new int[] {x, c};
            list.add(item);
        }
        
        return list;
    }
    
    /**
     * 获取一个数组的所有排列
     * @param arr
     * @return
     */
    public List<int[]> permutation(int[] arr) {
        int[] subArr = new int[arr.length - 1];
        System.arraycopy(arr, 0, subArr, 0, arr.length - 1);
        
        return permutation(subArr, arr[arr.length - 1]);
    }
    
    /**
     * 数组arr与a的所有排列组合
     * @param arr
     * @param a
     * @return
     */
    public List<int[]> permutation(int[] arr, int a) {
        List<int[]> list = new ArrayList<int[]>();
        if (arr.length == 0) {
            int[] item = new int[] {a};
            list.add(item);
            return list;
        }
        
        int[] subArr = new int[arr.length - 1];
        System.arraycopy(arr, 0, subArr, 0, arr.length - 1);
        List<int[]> subList = permutation(subArr, arr[arr.length - 1]);
        
        for (int[] aItem : subList) {
            int[] nItem = new int[aItem.length + 1];
            System.arraycopy(aItem, 0, nItem, 0, aItem.length);
            nItem[aItem.length] = a;
            list.add(nItem);
            
            int index = 0;
            while (index < nItem.length - 1) {
                int[] nnItem = new int[nItem.length];
                System.arraycopy(nItem, 0, nnItem, 0, nItem.length);
                int t = nnItem[index];
                nnItem[index] = nnItem[nItem.length - 1];
                nnItem[nItem.length - 1] = t;
                list.add(nnItem);
                index ++;
            }
        }
        
        return list;
    }
    
    /**
     * 数组列表去重
     * @param dataList
     * @return
     */
    public List<int[]> removeDuplicate(List<int[]> dataList) {
        List<int[]> list = new ArrayList<int[]>();
        Set<String> set = new HashSet<String>();
        
        for (int[] item : dataList) {
            StringJoiner sj = new StringJoiner(",");
            for (int i=0; i<item.length; i++) {
                sj.add(String.valueOf(item[i]));
            }
            
            String key = sj.toString();
            if (!set.contains(key)) {
                list.add(item);
                set.add(key);
            }
        }
        
        return list;
    }
    
    public String array2String(int[] arr) {
        StringJoiner sj = new StringJoiner(",", "[", "]");
        for (int i=0; i<arr.length; i++) {
            sj.add(String.valueOf(arr[i]));
        }
        
        return sj.toString();
    }
    
    /**
     * 检查4个数是否能得到24点
     * @param a
     * @param b
     * @param c
     * @param d
     * @return
     */
    public boolean check24Point(int a, int b, int c, int d) {
        int[] arr = new int[] {a, b, c, d};
        
        // 4个数所有排列，并去重
        List<int[]> fourList = permutation(arr);
        fourList = removeDuplicate(fourList);

        // 4个数简化成3个数，并去重
        List<int[]> threeList = new ArrayList<int[]>();
        for (int[] item : fourList) {
            List<Integer> fsList = calc(item[0], item[1]);
            for (Integer x : fsList) {
                int[] tItem = new int[] {x, item[2], item[3]};
                List<int[]> subList = permutation(tItem);
                threeList.addAll(subList);
            }
        }
        
        threeList = removeDuplicate(threeList);
        
        // 3个数简化成2个数，并去重
        List<int[]> twoList = new ArrayList<int[]>();
        for (int[] item : threeList) {
            List<int[]> subList = simplify(item[0], item[1], item[2]);
            twoList.addAll(subList);
        }
        
        twoList = removeDuplicate(twoList);
        
        // 校验2个数是否能得到24点
        boolean flag = false;
        for (int[] item : twoList) {
            if (check(item[0], item[1]) != NONE) {
                System.out.println(item[0] + " " + item[1]);
                flag = true;
            }
        }
        
        return flag;
    }
    
    public static void main(String[] args) {
        Game24Point g = new Game24Point();
        int[] arr = g.random();
        boolean b = g.check24Point(arr[0], arr[1], arr[2], arr[3]);
        String result = g.array2String(arr) + (b?"":"不") + "可以得到24点";
        System.out.println(result);
    }
}
